iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 3
0

為什麼要了解?

在我還是個剛轉職成功,沒有實際接觸過複雜專案的菜雞時期,面對新功能的開發,心態上保持著 先求有再求好,寫出許許多多用了不同內建函式、自訂函式的程式碼。新功能當然是順利開發成功,為此感到十分開心。這時候的我,對於能完成新功能開發的自己,感到十分得意。

工作經驗增加後,有機會碰到公司內較複雜的專案,藉此打開我的眼界,程式碼的部分沒有毫無章法的寫法,反倒是有一定規律的做法(現在的我知道這是 Design Pattern),當時我負責接觸的部分是效能優化的部分,這時候才感覺到沒有思考每種資料結構特性,胡亂使用順眼的函式執行,是一件多麽可怕的事情。

回憶結束。

關於程式碼的效率,可以從兩個角度來思考:

  • 執行速度可以多快?
  • 執行時期記憶體使用量有多少?

菜雞時期接觸的專案,鮮少有大數量(萬筆以上)的資料庫,或是每天接受的 Request 數量到達幾十萬甚至是幾百萬。因此在處理資料上都是小數量為主,任何的函式在執行上看不太出來效率的差異。但是,真實世界,尤其是開發逐漸上軌道的產品,不可能面對小數量,而是讓人無法有人平估的大數量。是否善用資料結構與演算法來優化產品的邏輯運算,在這個時候就派上用場了。當然,除了優化處理效率外,還有許多跟部署有關的技術可以優化大數量的 Request,這不在本文討論的範圍內。

回到主題,判斷執行速度與記憶體的使用,可以這樣理解:

時間複雜度,Time Complexity

強調需要執行的次數。

專業上的講法會提到測量方式、測試次數的加總以及如何用 Big O 表達,個人傾向簡單講解,面對一組資料,用 for-loop 執行嗎?假如面對多組資料,能避開巢狀 for-loop 嗎?有想過在 for-loop 調整執行的內容,好減少執行的次數。

空間複雜度,Space Complexity

強調變數的使用量。

專業上的講法會提到執行時要佔用的記憶體空間,個人傾向簡單講解,面對一組資料,是否要額外宣告變數來處理?變數的數量可以控制嗎?

two sum 這題該怎麼看待

暴力解

const twoSum = (nums, target) => {
  for (let i = 0; i < nums.length; i++) { // 第一個迴圈
    for (let j = i + 1; j < nums.length; j++) { // 第二個迴圈
      if (nums[j] = target - nums[i]) {
        return [i, j];
      }
    }
  }

  return [];
}

時間複雜度的部分,第一個迴圈,陣列內每一個項目都要被執行一遍,所以執行次數是 nums.length,在分析時習慣用 N 表達。針對陣列內每一個項目,會需要第二個迴圈,執行次數是 nums.length - 1,分析用 N-1 表達。

因此這題的時間複雜度是:

O(N * (N-1))
-> O(N^2 - N) // 相乘
-> O(N^2) // 只保留最大的數字

空間複雜度方面,沒有額外宣告任何變數。

因此,暴力解在執行時間方面會是 O(N^2),記憶體方面幾乎沒有大負擔。

使用 Hash Table

const twoSum = (nums, target) => {
    const comp = {}; // 額外宣告的變數

    for (let i=0; i<nums.length; i++){ // 第一個迴圈
        if (comp[ nums[i] ] >= 0 ) {
            return [ comp[nums[i] ], i]
        }

        comp[target-nums[i]] = i
    }
};

時間複雜度的部分,僅僅只有一個迴圈,執行次數是 nums.length

因此這題的時間複雜度是:O(N)

空間複雜度方面,額外宣告 Hash Table,隨著 N 的數量增長,Hash Table 內的資料量將跟著成長。

因此,Hash Table 在執行時間方面會是 O(N),記憶體方面則有負擔。

題外話

Imgur

這題嘗試用不同語言撰寫,有趣的地方在於,我直覺認為靜態語言就是比動態語言快速,殊不知 C# 賞我一巴掌,而記憶體的使用方面,JavaC# 也賞我兩巴賞。這邊有幾點可以推論:

  • 這題的寫法,在記憶體的存取方面,對於 JavaC# 有比較大的負擔。
  • LeetCode 官方的模擬環境,與我認知的不太一樣。
  • Golang 出人意料的快速,怪不得 Google 自誇是 21 世紀的 C 語言。

就我個人經驗而言,撰寫 JSJava 的時候幾乎沒在管記憶體,追求的只有更高的效率。直到接觸用 C 開發的機器,被 free 給嚇到,給我一個機會省思過度宣告變數的好壞。

結語

任何專業領域都一定有測不準原理的窘境,在程式設計的便是記憶體與時間的抉擇。拜摩爾定律協助半導體產業的發展,記憶體朝向大儲存量與低廉價格發展,使得空間複雜度變成次要,時間複雜度成為主要關注的重點。最典型的運用便是各式各樣的網頁,使用者不能忍受3秒以上的等待,於是瀏覽器們著重在使用記憶體,好帶給使用者快速的體驗。

那有著重空間複雜度的場合嗎?有的,在部分伺服器、嵌入式系統等,提供的是有限的記憶體,此時該思考如何在有限的記憶體下,爭取到多少時間?

當然,目前各大公司提到演算法時,仍舊著重在時間複雜度,記憶體的問題在特定產業才有可能遇到,因此,寫出能夠快速執行的程式碼幾乎是各大公司要求的基本功。


上一篇
Day 02: 刷 LeetCode 該有的基本知識
下一篇
Day 04: 從資料結構談起
系列文
你總是躲不掉的,不如放膽面對 LeetCode 吧!31
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言